/**
 * @file reviewBST.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2022-03-03
 *
 * @copyright Copyright (c) 2022
 *
 */

/**
 * BST: 中序遍历递增 如果用递归法就要想方设法用中序遍历
 *
 * 700.BST树中的搜索（递归+迭代）
 * 98.验证BST：方法一（中序遍历放入数组遍历一遍判断是否有序）；
 *            方法二（中序遍历递归（需要满足左子树最大值<root->val））
 * 530. BST树的最小绝对差 == 783.BST树节点最小距离
 *      已经是BST树了，中序递增，那么最小差只能是相邻点，和98.一样
 * 501.BST树中的众数 （众数可能不止一个）
 *      众数可能不止一个，那么必须用数组存储了呀，如果出现频次更高的数，清空res数组
 * 235.BST树的最近公共祖先
 *      对p、q位置讨论：（均在左、均在右、一左一右）
 * 236.二叉树的最近公共祖先
 *      也是对p、q位置的讨论，但是普通二叉树只能通过遍历，而后序是天然回溯，优先处理叶子节点
 *
 * BST的插入删除：莫名想起被红黑树支配的恐怖
 * 701.BST树的插入：递归+迭代（记录父节点） 简单（因为不用重构树）
 * 450.BST树的删除：删除+调整。
 *      调整：叶子节点、有一个孩子、有2个孩子（左子树接到右子树最左 或 右子树接在左子树最右）
 * 669.修剪BST树：看起来难做起来简单
 *      不用固定对BST树的处理模式，打开思路，root和low、high有啥关系？
 *      root在[low,high]内还是返回root，递归处理左右子树；不在那就更简单了处理一个子树就行了
 * 108.有序数组转换为BST树：类似二分查找，从mid开始建树
 * 538.BST树转换成累加树：如果是一个有序数组该如何求这种累加？倒着累加呗，那么就逆中序遍历倒着加呗
 * 
 */

#include <algorithm>
#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution98
{
  public:
    long long lastVal = INT64_MIN; // 记录上一个节点的值
    bool isValidBST(TreeNode *root)
    {
        if (root == nullptr) {
            return true;
        }
        // 中序
        bool left = isValidBST(root->left);
        if (lastVal < root->val) {
            lastVal = root->val;
        } else {
            return false;
        }
        bool right = isValidBST(root->right);
        return left && right;
    }
};

class Solution530
{
  public:
    int lastVal = -1;
    int minDiff = 100000;
    int getMinimumDifference(TreeNode *root)
    {
        traversal(root);
        return minDiff;
    }

    void traversal(TreeNode *root)
    {
        if (root == nullptr) {
            return;
        }
        // 中序
        traversal(root->left);
        if (-1 != lastVal) {
            minDiff = min(minDiff, root->val - lastVal);
        }
        lastVal = root->val;
        traversal(root->right);
    }
};

class Solution501
{
  public:
    int cnt = 0; // 记录数的频次
    int maxCnt = 0;
    int lastVal = -100001;
    vector<int> res;
    vector<int> findMode(TreeNode *root)
    {
        traversal(root);
        return res;
    }

    void traversal(TreeNode *root)
    {
        if (root == nullptr) {
            return;
        }
        traversal(root->left);
        if (-100001 != lastVal && lastVal == root->val) {
            ++cnt;
        } else {
            cnt = 1;
        }
        lastVal = root->val; // 记录上一个数
        if (maxCnt == cnt) {
            res.push_back(lastVal);
        } else if (maxCnt < cnt) {
            res.clear();
            maxCnt = cnt;
            res.push_back(root->val);
        }
        traversal(root->right);
    }
};

class Solution236
{
  public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        // 出口：找到一个节点等于p、q
        if (root == nullptr) {
            return nullptr;
        }
        if (root == p || root == q) {
            return root;
        }
        // 后序是天然回溯，最先处理的是叶子结点
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if (left && right) { // p、q分布在左右子树
            return root;
        }
        if (left == nullptr) { // p、q不在左子树，那就返回右子树
            return right;
        } else {
            return left;
        }
    }
};

class Solution450
{
  public:
    TreeNode *deleteNode(TreeNode *root, int key)
    {
        // 搜索+调整
        if (root == nullptr) {
            return nullptr;
        }
        if (key == root->val) {
            if (root->left == nullptr && root->right == nullptr) { // 叶子
                return nullptr;
            } else if (root->left == nullptr) { // 有右孩子
                return root->right;
            } else if (root->right == nullptr) { // 有左孩子
                return root->left;
            } else { // 有2个孩子，返回左孩子，右孩子接在左子树最右
                //  或 返回右孩子，左孩子接在右子树最左
                TreeNode *cur = root->left;
                while (cur->right) {
                    cur = cur->right;
                }
                cur->right = root->right;
                return root->left;
            }
        } else if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else {
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};